package 下一个更大元素II;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * createTime: 2025/5/24 22:57
 * description:
 * 给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
 * 示例 1:
 * 输入: [1,2,1]
 * 输出: [2,-1,2]
 * 解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
 * 提示:
 * 1 <= nums.length <= 10^4
 * -10^9 <= nums[i] <= 10^9
 *
 * @author AirMan
 */
public class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // 很明显这是数组中寻找一个数字后面的最值问题 ==> 单调栈
        // 单调栈就是利用一个栈存放还未找到最值的索引，当单调栈是递增序列的时候，寻找的是右边的第一个最大值
        // 当单调栈是递减序列的时候，寻找的就是右边的第一个最小的值

        Deque<Integer> stack = new LinkedList<>();
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        int size = nums.length;
        // 一共需要循环 2 * nums.length，达到"循环"的效果，以此来寻找循环中的"右边"第一个最大值
        for (int i = 0; i < 2 * size; i++) {
            // 如果栈为空，说明前面的数字都寻找完了
            if (stack.isEmpty() && i < size) {
                stack.push(i % size);
                continue;
            }
            // 比较栈顶所代表的值，和当前值的大小，如果当前值大于栈顶元素所代表的值，就代表找到了右边的第一个最值
            int topIndex = stack.peek();
            while (nums[i % size] > nums[topIndex]) {
                result[topIndex] = nums[i % size];
                // 将确定的索引出栈
                stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                topIndex = stack.peek();
            }
            // 如果当前元素还未确定，就入栈
            if (i < size) {
                stack.push(i % nums.length);
            }
        }
        return result;

    }
}
